package arr.数组中的重复数据;

//给定一个整数数组 doubleDimensionalArrayPrint，其中1 ≤ doubleDimensionalArrayPrint[i] ≤ n （n为数组长度）, 其中有些元素出现两次而其他元素出现一次。
//
// 找到所有出现两次的元素。
//
// 你可以不用到任何额外空间并在O(n)时间复杂度内解决这个问题吗？
//
// 示例：
//
//
//输入:
//[4,3,2,7,8,2,3,1]
//
//输出:
//[2,3]
//
// Related Topics 数组
// 👍 347 👎 0


import java.util.ArrayList;
import java.util.List;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        List<Integer> list = new ArrayList<>();
        int n = nums.length;
        for (Integer integer : nums) {
            nums[(integer - 1) % n] = nums[(integer - 1) % n] + n;
        }
        for (int i = 0; i < n; i++) {
            if (nums[i] > 2 * n){
                list.add(i + 1);
            }

        }
        return list;
    }

    public static void main(String[] args) {
        int [] a ={4,3,2,7,8,2,3,1};
        Solution solution =new Solution();
        System.out.println(solution.findDuplicates(a).toString());
    }
}
//leetcode submit region end(Prohibit modification and deletion)
